Homework: https://work.caltech.edu/homework/hw3.pdf

Answers:

b
c
d
a --> b ✔ (any 3 points can make a plane)
e --> b ✔ (either it is 2^N if there is no breakpoint else it is polynomial)
c
c
d
b --> d ✔ (you can think of points on a circle and then shattering them with a triangle shape)
e --> b ✔ (3 is the breakpoint; NC0 + NC1 + NC2 == (N+1)C2 + 1)

Answer key: https://work.caltech.edu/homework/hw3_sol.pdf



In [2]:

    
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
from IPython.display import display
from numpy.linalg import inv



In [ ]:

    
# probability >= 2 * M * e^(-2 * epsilon^2 * N)
# log (2 * M / probability) <= 2 * epsilon^2 * N
# N >= log (2 * M / probability) / 2 * epsilon^2



In [7]:

    
probability = 0.03
epsilon = 0.05
M = 1
N = np.log (2 * M / probability) / (2 * epsilon ** 2)
print "Answer 1: {}({})".format(np.ceil(N), N)









    



Answer 1: 840.0(839.941015576)



In [8]:

    
probability = 0.03
epsilon = 0.05
M = 10
N = np.log (2 * M / probability) / (2 * epsilon ** 2)
print "Answer 2: {}({})".format(np.ceil(N), N)









    



Answer 1: 1301.0(1300.45803417)



In [9]:

    
probability = 0.03
epsilon = 0.05
M = 100
N = np.log (2 * M / probability) / (2 * epsilon ** 2)
print "Answer 3: {}({})".format(np.ceil(N), N)









    



Answer 3: 1761.0(1760.97505277)



In [ ]: